package com.dyz.leetcode._01_array;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class _54_spiralOrder {
    public List<Integer> spiralOrder(int[][] matrix) {

        List<Integer> res = new ArrayList<>();
        int m = matrix.length;
        int n = matrix[0].length;

        int[][] dirs = {{0,1},{1,0},{0,-1},{-1,0}};
        int row = 0;
        int col = 0;
        int dir = 0;
        //定义填充过的格子
        boolean[][] isVisit = new boolean[m][n];
        for(int i=0; i< m*n; i++){
            res.add(matrix[row][col]);
            isVisit[row][col] = true;
            //下一个格子
            int nextRow = row + dirs[dir][0];
            int nextCol = col + dirs[dir][1];
            //判断格子是否超出界限
            if(nextRow<0 || nextRow>=m || nextCol<0||nextCol>=n||isVisit[nextRow][nextCol]){
                //若超出格子，需要变换dir
                dir = (dir+1) % 4;
            }
            row = row+dirs[dir][0];
            col = col +dirs[dir][1];
        }
        return res;
    }

    public List<Integer> spiralOrder1(int[][] matrix) {
        List<Integer> res = new ArrayList<>();
        int m = matrix.length;
        int n = matrix[0].length;
        int startRow = 0;
        int endRow = m -1;
        int startCol = 0;
        int endCol = n-1;

        while(startRow<=endRow && startCol<=endCol){
            //top
            for(int col = startCol; col<= endCol; col++){
                res.add(matrix[startRow][col]);
            }
            startRow++;
            if(startRow>endRow){
                break;
            }
            //right
            for(int row = startRow; row<=endRow; row++){
                res.add(matrix[row][endCol]);
            }
            endCol--;
            if(startCol>endCol){
                break;
            }
            //buttom
            for(int col = endCol; col>=startCol; col--){
                res.add(matrix[endRow][col]);
            }
            endRow--;
            if(startRow>endRow){
                break;
            }
            //left
            for(int row=endRow; row>=startRow; row--){
                res.add(matrix[row][startCol]);
            }
            startCol++;

            if(startCol>endCol){
                break;
            }
        }
        return res;
    }

    public static void main(String[] args) {
        int[][] matrix = {{1,2,3,4},{5,6,7,8},{9,10,11,12}};
        List<Integer> integers = new _54_spiralOrder().spiralOrder1(matrix);
        System.out.println(integers);
    }
}
